import java.util.PriorityQueue;

public class Test {
	/**
	 * topK问题
	 * 前k个最大的数，建小堆，然后依次比较大小，
	 * 前k个最小的数，建大堆，然后依次比较大小，这个堆中就是前k个大的或小的数
	 * 第k个大的，最后返回堆顶的数就行了
	 * @param args
	 */
	public static void main(String[] args) {
		int [] array={ 27,15,19,18,28,34,65,49,25,37 };
		PriorityQueue<Integer> pq=new PriorityQueue<>(3);
		for(int i=0;i<3;i++) {
			pq.offer(array[i]);
		}
		for(int i= 3;i<array.length;i++) {
			if(array[i]>pq.peek()) {
				pq.poll();
				pq.offer(array[i]);
			}
		}
		System.out.println("===========");
	}
	public static void main3(String[] args) {
		HeapTest heap=new HeapTest();
		int [] array={ 27,15,19,18,28,34,65,49,25,37 };
		heap.initHeap(array);
		heap.createHeapDown();
		heap.display();
	}
	public static void main2(String[] args) {
		HeapTest heap=new HeapTest();
		int [] array={ 27,15,19,18,28,34,65,49,25,37 };
		heap.initHeap(array);
		heap.createHeapDown();
		//在堆排序之前先进行建堆，
		heap.heapSort();
		heap.display();
	}
	public static void main1(String[] args) {
		HeapTest heap=new HeapTest();
		int [] array={ 27,15,19,18,28,34,65,49,25,37 };
		heap.initHeap(array);
		heap.createHeapDown();
		heap.display();
		System.out.println();
		heap.offer(1);
		heap.display();
		System.out.println(heap.poll());
	}
}
